/*--------------------------------------------------------------------------------
* Copyright (c) 2022,西北农林科技大学信息学院计算机科学系
* All rights reserved.
*
* 文件名称：main.c
* 文件标识：见配置管理计划书
* 摘要：颠倒句子中单词，利用句子栈和单词栈实现。
*       首先遍历修剪和压缩后的句字符串逐字符压入句子栈。
*       再出栈各个字符(句子逆序)，如果不是空格，则压入单词栈。
*       最后出栈单词栈中的字符写入字符串(单词逆序)。
*       每写完一个单词，则添加指定的分隔符。
*       最终添加句子终止字符和字符串终止符。
*
* 当前版本：1.0
* 作者：耿楠
* 完成日期：2022年11月27日
*
* 取代版本：无
* 原作者：耿楠
* 完成日期：
------------------------------------------------------------------------------------*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

/* 栈结点(单词)结构体 */
typedef struct _node
{
    char ch;            /* 字符数据 */
    struct _node *next; /* 指向下一个单词的指针 */
}node;

/* 栈结构体 */
typedef struct _stack_type
{
    node *top;
}*Stack;

/* 栈操作 */
Stack create(void);
void destroy(Stack);
void make_empty(Stack);
int is_empty(Stack);
int is_full(Stack);
void push(Stack, const char);
char pop(Stack);

/* 分割符修剪与压缩 */
char *trimString(char*, const char*);
char *removeDupSpaces(char*, const char*);

/* 判断是否为一个句子 */
int isSentence(const char *, const char *, const char *);
/* 颠倒句子中的单词 */
char* revSentenceWords(char *, const char *, const char *, const char *);

/* 错误响应 */
static void errormsg(const char *);

int main()
{
    /* 句子 */
    /* char s[] = "you can cage a swallow can't you?"; */
    char s[] = "   you can \n  cage a \tswallow  \ncan't you?   ";

    /* 原句子单词分隔符 */
    char delim[] = " \t\n\r";
    /* 句子终止符 */
    char term[] = ".?!";
    /* 结果句子单词分隔符 */
    char hyphen[] = " ";
    char *str = NULL;

    if(isSentence(s, delim, term))
    {
        str = revSentenceWords(s, delim, term, hyphen);
        if(str != NULL)
        {
            puts(str);
        }
    }

    return 0;
}

/* 错误响应 */
static void errormsg(const char *message)
{
    printf("%s\n", message);
    exit(EXIT_FAILURE);
}

/*---------------------------------------------------------
// 名称：char *trimString(char *s, const char *delim)
// 功能：删除字符串首尾的分隔字符(空白)
// 参数：
//       [char* s] ------------- 待处理的字符串指针
//       [const char* delim] --- 分隔字符集指针
// 返回：[char *] --- 结果字符串
// 作者：耿楠
// 日期：2022年11月27日
--------------------------------------------------------*/
char *trimString(char *s, const char *delim)
{
    size_t len;

    /* 删除前导分隔符(空白) */
    while(strchr(delim, *s))
    {
        s++;
    }

    /* 删除尾部分隔符(空白) */
    len = strlen(s);
    while(strchr(delim, s[len - 1]))
    {
        s[len - 1] = '\0';
        len--;
    }

    return s;
}

/*---------------------------------------------------------
// 名称：char *removeDupSpaces(char *s, const char *delim)
// 功能：将字符串中指定的分隔字符集中的字符压缩并替换为1个空格。
// 参数：
//       [char* s] ------------- 待处理的字符串指针
//       [const char* delim] --- 分隔字符集指针
// 返回：[char *] --- 结果字符串
// 作者：耿楠
// 日期：2022年11月27日
--------------------------------------------------------*/
char *removeDupSpaces(char *s, const char *delim)
{
    int  pos = 0;
    size_t len;
    char *p;

    s = trimString(s, delim);

    /* 删除内部重复分隔符 */
    while(*(s + pos))
    {
        /* 连续两个分隔符 */
        if(strchr(delim, *(s + pos)) && strchr(delim, *(s + pos + 1)))
        {
            /* 指向下一个分隔符，并替换为空格 */
            p = s + pos + 1;
            *p = ' ';

            /* 将后续内容向前移动1个位置 */
            len = strlen(p);
            memmove(p - 1, p, len + 1);
        }
        else
        {
            /* 记录下一个位置 */
            pos++;
        }
    }

    *(s + pos) = '\0';

   return s;
}

/*------------------------------------------------------------------------
// 名称：int isSentence(const char *s, const char *delim, const char *term)
// 功能：判断句子是否有句子终止字符。
// 算法：找到句子尾部不是分隔符(空白)的字符，判断其是不是句子终止字符。
// 参数：
//       [char* s] -------------- 待逆序的字符串的指针
//       [const char* delim] ---- 单词单词分隔字符集指针
//       [const char* term] ----- 句子终止字符集指针
// 返回：[int] --- 有则返回1, 无则返回0
// 作者：耿楠
// 日期：2022年11月27日
------------------------------------------------------------------------*/
int isSentence(const char *s, const char *delim, const char *term)
{
    size_t len = 0;

    len = strlen(s);

    /* 删除尾部分隔符(空白) */
    len = strlen(s) - 1;
    while(strchr(delim, s[len]) && len >= 0)
    {
        len--;
    }

    /* 判断最后有没有句子终止字符 */
    if(!strchr(term, s[len]))
    {
        return 0;
    }

    return 1;
}

/*------------------------------------------------------------------------
// 名称：char* revSentenceWords(char *s, const char *delim,
//                              const char *term, const char *hyphen)
// 功能：将句子按单词逆序(单词必须以空格分隔)。
// 算法：首先构建一个记录单词的栈，然后采用弹出单词，在原字符串空间拼接结果。
// 参数：
//       [char* s] -------------- 待逆序的字符串的指针
//       [const char* delim] ---- 单词单词分隔字符集指针
//       [const char* term] ----- 句子终止字符集指针
//       [const char* hyphen] --- 结果单词分隔字符集指针
// 返回：[char*] --- 逆序后字符串的指针
// 作者：耿楠
// 日期：2022年11月27日
// 注意：处理过程会对原字符串进行改写，如需要保留原串，请在调用该函数前备份。
------------------------------------------------------------------------*/
char* revSentenceWords(char *s, const char *delim,
                       const char *term, const char *hyphen)
{
    char ch, *p;
    char terminator = 0;
    size_t str_len = 0;
    /* 单词栈 */
    Stack s_stack = NULL;
    Stack w_stack = NULL;

    /* 修剪和压缩分隔符(替换为1个空格) */
    s = trimString(s, delim);
    s = removeDupSpaces(s, delim);
    str_len = strlen(s);

    /* 记录句子终止字符并删除原句子终止字符 */
    terminator = s[str_len - 1];
    s[str_len - 1] = '\0';

    /* 构建句子栈(将句子中的字母逐一压入栈中) */
    p = s;
    s_stack = create();
    while(*p)
    {
        push(s_stack, *p);
        p++;
    }

    /* 清空原串 */
    *s = '\0';
    p = s;
    w_stack = create();

    /* 字符出栈(句子逆序) */
    while(!is_empty(s_stack))
    {
        ch = pop(s_stack);
        /* 如果不是空格，则压入单词栈 */
        while(ch != ' ')
        {
            push(w_stack, ch);
            if(is_empty(s_stack))
            {
                break;
            }
            ch = pop(s_stack);
        }

        /* 字符出栈(单词逆序)，写入结果字符串 */
        while(!is_empty(w_stack))
        {
            *p = pop(w_stack);
            p++;
        }
        *p = hyphen[0];
        p++;
    }

    /* 添加句子终止字符和字符串终止字符 */
    *(p - 1) = terminator;
    *p = '\0';

    /* 删除栈 */
    destroy(s_stack);
    destroy(w_stack);

    return s;
}

/*------------------------------------------------------------------------
// 名称：Stack create(void)
// 功能：创建栈。
// 参数：
//       [void] --- 无
// 返回：[Stack] --- 栈指针
// 作者：耿楠
// 日期：2022年11月27日
------------------------------------------------------------------------*/
Stack create(void)
{
    /* 为栈结构申请内存 */
    Stack s = (Stack)malloc(sizeof(struct _stack_type));
    if(s == NULL)
    {
        errormsg("Error in create: stack could not be created.");
    }

    /* 初始化栈成员 */
    s->top = NULL;

    return s;
}

/*------------------------------------------------------------------------
// 名称：void destroy(Stack s)
// 功能：销毁栈。
// 算法：先清空栈，再释放栈空间
// 参数：
//       [Stack s] --- 栈指针
// 返回：[void] --- 无
// 作者：耿楠
// 日期：2022年11月27日
------------------------------------------------------------------------*/
void destroy(Stack s)
{
    make_empty(s);
    free(s);
}

/*------------------------------------------------------------------------
// 名称：void make_empty(Stack s)
// 功能：清空栈。
// 算法：逐个弹出单词，再释放单词占用的空间
// 参数：
//       [Stack s] --- 栈指针
// 返回：[void] --- 无
// 作者：耿楠
// 日期：2022年11月27日
------------------------------------------------------------------------*/
void make_empty(Stack s)
{
    while(!is_empty(s))
    {
        pop(s);
    }
}

/*------------------------------------------------------------------------
// 名称：int is_empty(Stack s)
// 功能：判断栈是否为空。
// 参数：
//       [Stack s] --- 栈指针
// 返回：[int] --- 栈不为空返回1, 为空返回0
// 作者：耿楠
// 日期：2022年11月27日
------------------------------------------------------------------------*/
int is_empty(Stack s)
{
    return s->top == NULL;
}

/*------------------------------------------------------------------------
// 名称：int is_full(Stack s)
// 功能：判断栈是否为满。
// 参数：
//       [Stack s] --- 栈指针
// 返回：[int] --- 永远返回0，因为用链表实现，不会出现满栈现象
// 作者：耿楠
// 日期：2022年11月27日
------------------------------------------------------------------------*/
int is_full(Stack s)
{
    return 0;
}

/*------------------------------------------------------------------------
// 名称：void push(Stack s, char ch)
// 功能：将字母入栈。
// 参数：
//       [Stack s] --- 栈指针
//       [char ch] --- 被压栈的字母
// 返回：[void] --- 无
// 作者：耿楠
// 日期：2022年11月27日
------------------------------------------------------------------------*/
void push(Stack s, char ch)
{
    node *new_node = NULL;

    /* 创建新结点 */
    new_node = (node*)malloc(sizeof(node));
    if(new_node == NULL)
    {
        errormsg("Error in push: stack is full(not enough memory).");
    }

    /* 单词结构体成员赋值 */
    new_node->ch = ch;
    /* 单词结构体指针成员指向栈顶 */
    new_node->next = s->top;

    /* 调整栈顶指针 */
    s->top = new_node;
}

/*------------------------------------------------------------------------
// 名称：char pop(Stack s)
// 功能：将单词出栈。
// 参数：
//       [Stack s] ----- 栈指针
// 返回：[char] --- 弹出的字符
// 作者：耿楠
// 日期：2022年11月27日
------------------------------------------------------------------------*/
char pop(Stack s)
{
    node *old_top;
    char ch;

    /* 栈为空，结束程序 */
    if(is_empty(s))
    {
        errormsg("Error in pop: stack is empty.");
    }

    /* 记录链表头结点指针 */
    old_top = s->top;
    ch = old_top->ch;
    /* 调整栈顶指针 */
    s->top = old_top->next;

    /* 删除栈顶结点 */
    free(old_top);

    return ch;
}
